package com.atguigu.dp;

//2.斐波那契数列 - 递归+缓存
public class Demo02 {
    public static void main(String[] args) {
        for(int i = 0 ; i<=100 ; i++){
            System.out.println(i+"  :  " + fn(i));
        }
    }

    private static long[] cache = new long[101];

    public static long fn(int n){
        if(n==0){
            return 0 ;
        }
        if(n==1){
            return 1 ;
        }
        if(cache[n]!=0){
            return cache[n];
        }else{
            long result = fn(n-1)+fn(n-2);
            cache[n] = result ;
            return result;
        }

    }
}
